package structure.linkedList;

import java.util.Comparator;
import java.util.PriorityQueue;

public class LeetCode_148 {

    public static void main(String[] args) {
        ListNode node = new ListNode(4);
        node.next = new ListNode(3);
        node.next.next = new ListNode(1);
        node.next.next.next = new ListNode(2);
        ListNode listNode = new LeetCode_148().sortList(node);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        ListNode cur = head;
        while(cur!=null){
            queue.offer(cur);
            cur = cur.next;
        }

        ListNode prev = new ListNode(0);
        cur = prev;
        while(!queue.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
        }
        return prev.next;
    }



        public ListNode sortList1(ListNode head) {
        return sortList(head, null);

    }

    private ListNode sortList(ListNode head, ListNode tail) {
        if (head == null || head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode fast = head, slow = head;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode left = sortList(head, slow);
        ListNode right = sortList(slow, tail);
        return mergeList(left, right);
    }


    public ListNode mergeList(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeList(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeList(l2.next, l1);
            return l2;
        }
    }
}
